백준 2250 트리의 높이와 너비는 트리의 노드에 번호를 붙이고, 같은 레벨에 있는 최대 노드 번호 - 최소노드 번호 +1의 값이 가장 큰 즉 너비가 가장 넓은 레벨과 너비의 값을 출력하는 문제이다.
이 과정에서 트리의 번호를 어떻게 매기는가는 문제의 그림을 보면 쉽게 알 수 있다. 위에서 2번 번호를 가진 노드를 보자. 2번을 기준으로 번호를 매길 때 왼쪽 끝까지 들어가서 번호를 매기는 것을 볼 수 있고 오른쪽 자식들의 경우 왼쪽을 우선적으로 매기고 오른쪽을 나중에 매기는 것을 알 수 있다. -> 따라서 이 경우 중위 순회를 하며 index를 매기고 있다.
즉 이 문제는 들어온 입력값으로 트리를 구성한 뒤 중위 순회로 번호를 매기고 같은 레벨에서의 최소, 최대 번호 값을 찾아 비교하는 문제이다.
입력값이 10000까지 들어오고 노드의 번호는 불규칙 할 수 있기 때문에 먼저 n개의 노드를 생성하고 배열에 저장했다. 생성한 노드는 입력값인 root, left, right의 해당 노드를 배열에서 찾아 연결하며 트리를 구성했다. 그리고 여기서 가장 중요한 점은 root가 항상 1번 노드가 아니라는 점이다. -> 이 예외를 찾지 못해 고생했다.
1번 노드가 아니기 때문에 배열을 하나 더 만들어서 자신이 자식으로 들어가면 flag를 채운뒤 나중에 flag가 없는 번호의 노드가 root가 될 것이기 때문에 이 방법으로 루트를 찾았다.
그 다음 레벨 별로 트리의 너비를 계산하기 위해 레벨 순회를 하며 최소 번호값과 최대 번호값을 찾으며 마지막에는 이전의 값과 비교하여 최대인지 확인한다.
int mn = INF; int mx = -INF; typedefstructNode { int idx; Node* left; Node* right; }Node;
Node* arr[10001];
int isChild[10001];
voiddfs(Node** current) { if ((*current)->left != NULL) dfs(&(*current)->left);
(*current)->idx = numb++;
if ((*current)->right != NULL) dfs(&(*current)->right); }
voidlevelOrder(Node** cur, int d,int level) { if (d == level) { mn = min(mn, (*cur)->idx); mx = max(mx, (*cur)->idx); } if ((*cur)->left != NULL) levelOrder(&(*cur)->left, d + 1, level); if ((*cur)->right != NULL) levelOrder(&(*cur)->right, d + 1, level); }
intmain() { //freopen("input.txt", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++) { arr[i] = new Node({ -1, NULL, NULL }); }
for (int i = 1; i <= n; i++) { int root, left, right; cin >> root >> left >> right; if (left != -1) { arr[root]->left = arr[left]; isChild[left] = 1; } if (right != -1) { arr[root]->right = arr[right]; isChild[right] = 1; } }
int root = -1; for (int i = 1; i <= n; i++) { if (isChild[i] == 0) { root = i; break; } }
dfs(&arr[root]);
int h = (int)ceil(log2(n)); int ret = 0; int retidx = -1; for (int i = 1; i <= h + 1; i++) { mn = INF; mx = -INF; levelOrder(&arr[root], 1, i); if (ret < mx - mn + 1) { ret = mx - mn + 1; retidx = i; } }
cout << retidx << ' ' << ret << endl;
return0;
}
포스트
톰캣 부팅속도 빠르게
Tomcat 부팅속도 너무 느린문제tomcat을 여러번 stop & start 했더니 다음과 같은 에러가 발생 connection이 실패 했다..? -> tomcat이 사용하는 8080과 사용하는 것 같은 다른포트들은 열려있는데 정작 톰캣 서버포트인 300
백준 12100 2048 easy
백준 2048 문제는 2048 게임을 간단하게 시뮬레이션 해보는 문제이다. -> 왼쪽, 오른쪽, 위, 아래의 방향으로 움직였을 경우 숫자들이 합쳐지는 것만 구현한다면 dfs로 그리 어렵지 않게 풀 수 있는 문제이다. 단순히 생각대로 위, 아래, 오른쪽, 왼쪽 함수
백준 13459 째로탈출
백준 째로 탈출은 10번이라는 횟수의 제한 안에 파란 구슬을 빼지 않으면서 빨간 구슬을 뺄 수 있는지 시뮬레이션을 해보는 문제이다. bfs를 통해서 현재 빨간 구슬, 파란구슬의 위치에 대해 상,하, 좌,우 움직인 좌표가 어디인지를 확인해 나가면 풀 수 있는 문제이다.
백준 3190 뱀
백준 3190 뱀은 도스 뱀 게임을 구현하는 문제이다. n*n의 맵이 있다고 가정하고 0,0의 배열의 위치에서 뱀이 시작했을 때 과연 뱀이 몇초후에 죽는지 출력하는 문제이다. 방향 전환 정보와 사과의 위치 정보가 주어지게 되는데 이 뱀을 잘 구현하기 위해서는 list
백준 14500 테트로미노
백준 테트로미노는 n * m 배열에 적혀 있는 숫자에 도형을 넣은뒤 도형이 놓여지는 숫자들의 합이 최대로 되게 하는 문제이다. 이 문제는 단순히 도형 하나씩을 넣어보면 되기 때문에 빈틈없이 꽉 채우는 타일링 문제보다 쉬운 것 같다. 먼저 0,0을 기준으로 도형의 상대적